'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-10 20:35:18
'''
'''
39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]
示例 2：

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
 

提示：

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500


tips:难点在于每个元素可以出现多次，如果一个元素出现一次，直接用或者不用该元素即可，简单递归。出现多次，就需要
对同一元素数数了，递归代码如下
'''

from typing import List
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        tmp = []
        import copy
        def recurse(cur):
            # print(cur, tmp)
            
            if sum(tmp) == target:
                ans.append(copy.copy(tmp))
                return
            if cur>=len(candidates):
                return
            # if sum(tmp) >= target:
            #     return
            cnt=0
            while sum(tmp)<target:
                tmp.append(candidates[cur])
                cnt+=1
                recurse(cur+1)
            while cnt:
                tmp.pop()
                cnt-=1
            recurse(cur+1)
        recurse(0)
        return ans
if __name__ == "__main__":
    solution = Solution()
    candidates = [2,3,6,7]
    target = 7
    print(solution.combinationSum(candidates, target))